#include<stdio.h>
void PrintArray(int *a,int size)
{
    for(int i= 0;i<size;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}
void Swap(int *a,int *b)
{
    int temp=0;
    temp=*a;
    *a=*b;
    *b=temp;
}
void BubbleSort(int *a,int size)
{
    for(int i=0;i<size-1;i++)
    {
        int flag=0;
        for(int j=0;j<size-i-1;j++)
        {
            if(a[j]>a[j+1])
            {
                flag=1;
                Swap(&a[j],&a[j+1]);
            }
        }
        if(flag==0)
        {
            break;
        }
    }
}
//插入排序
void InsertSort (int *a,int size)
{
    for(int i=1;i<size;i++)
    {
         int j=i;//这个位置是即将要插入的树
         int temp=a[j];
         for(;j>0;j--)
         {
            if(a[j-1]>temp)
            {
                a[j]=a[j-1];
            }
            else
            {
                break;
            }
         }
         a[j]=temp;
    }
}
//选择排序
void ChooseSort(int *a,int size)
{
    for(int i=0;i<size-1;i++)
    {
        int min=i;
        for(int j=i+1;j<size;j++)
        {
            if(a[min]>a[j])
            {
                min=j;
            }
        }
        Swap(&a[min],&a[i]);
    }
}
//选择2,双指针算法，两个指针的算法叫双指针算法
void ChooseSort2(int *a,int size)
{
    int left=0;
    int right=size-1;
    while(left<right)
    {
        int min=left;
        int max=right;
        for(int i=left;i<=right;i++)
        {
            if(a[i]<a[min])
            min=i;
            if(a[i]>a[max])
            max=i;
        }
        Swap(&a[left],&a[min]);
        if(max==left)//当极值在两端时
        {
            max=min;
        }
        Swap(&a[right],&a[max]);
        left++;
        right--;
    }
}

//快速排序 双指针、递归、分治
void FastSort(int *a,int start,int end)
{
    if(start >=end)
         return ;
    int left =start;
    int right =end;
    int temp =a[start];
    while(left<right)
    {
        //从右向左找比基准值大的
        while(a[right]>temp&&left<right)
             right--;
        if(left<right)
             a[left++]=a[right];//把基准值小的数放到左边
        //从左往右找比基准值大的
        while(a[left]<temp&&left<right)
             left++;
        if(left<right)
             a[right--]=a[left];//把比基准值大的放右边  
    }
    a[left]=temp;
    FastSort(a,start,left-1);
    FastSort(a,right+1,end);
}
//返回找到的数组元素的下标
int BinarySearch(int *a,int size,int element)
{
    int left=0;
    int right=size-1;
    while(left<=right)
    {
        int mid=left+(right-left)/2;
        //(left&right)+((left^right)>>1);
        if(a[mid]==element)
        {
            return mid;
        }
        else if(a[mid]>element)
        {
            right=mid-1;
        }
        else if(a[mid]<element)
        {
            left=mid+1;
        }
    }
    return -1;

}
int main()
{
    int a[5]={8,65,24,2,5};
    PrintArray(a,5);
    //ChooseSort(a,5);
    //InsertSort(a,5);
    //ChooseSort2(a,5);
    FastSort(a,0,4);
    PrintArray(a,5);
    int index=BinarySearch(a,5,24);
    if(index==-1)
    {
        printf("没找到\n");
    }
    else
    {
        printf("找到了在%d位置\n",index);
    }
    PrintArray(a,5);
}


















































